#include "graph.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void allocate_vertexes_if_needed();
int  get_index_of_next_available_vertex();
void allocate_edges_if_needed();
int get_index_of_next_available_edge();
int get_vertex_id(char* name);
bool edge_already_exists(int first_vertex_id, int second_vertex_id);

#define MAX_ARRAY_SIZE 2
int number_of_available_vertexes = 0;
int allocated_vertexes = 0;

int number_of_available_edges = 0;
int allocated_edges = 0;

vertex ** arr_vertex = NULL;
edge ** arr_edges = NULL;
xmlDocPtr doc=NULL; 

void add_vertex (char* name)
{
	int index_to_insert;
	if (strlen(name) == 0)
	{
		printf("Error: When adding a vertex name must have at least one letter \n");
		return;
	}
	
	allocate_vertexes_if_needed();

	index_to_insert = get_index_of_next_available_vertex();

	arr_vertex[index_to_insert]->cluster = -1;
	arr_vertex[index_to_insert]->deleted = 0;
	arr_vertex[index_to_insert]->name =(char *) malloc((strlen(name) + 1) * sizeof(char));
	strcpy(arr_vertex[index_to_insert]->name, name);

	number_of_available_vertexes--;
}

void remove_vertex_by_name (char *name)
{
	int index_to_remove = -1;
	int i;
	for (i = 0 ; i < allocated_vertexes ; i++)
	{
		if (arr_vertex[i]->deleted == 0 && strcmp(arr_vertex[i]->name, name) == 0)
		{
			if (index_to_remove != -1)
			{
				printf("Error: More than one vertex with the requested name exists, please remove using id\n");
				return;
			}

			index_to_remove = i;
		}	
	}

	if (index_to_remove == -1)
	{
		printf("Error: Requested vertex does not exist\n");
		return;
	}
	
	remove_vertex_by_id(index_to_remove);
}

void remove_vertex_by_id(int id)
{
	int i;
	if (id >= allocated_vertexes || id < 0  || arr_vertex[id]->deleted == 1)
	{
		printf("Error: Requested vertex does not exist\n");
		return;
	}

	for (i = 0 ; i < allocated_edges ; i++)
	{
		if ((arr_edges[i]->deleted == 0) && (arr_edges[i]->v1_id == id || arr_edges[i]->v2_id == id))
		{
			printf("Cannot delete vertex %s since there are edges connected to it\n", arr_vertex[id]->name);
			return;
		}
	}

	arr_vertex[id]->deleted = 1;
	
	number_of_available_vertexes++;
}

void add_edge_by_name (char * first_vertex_name, char * second_vertex_name, double weight)
{
	int first_vertex_id = get_vertex_id(first_vertex_name);
	int second_vertex_id = get_vertex_id(second_vertex_name);

	if (first_vertex_id == -1 || second_vertex_id == -1)
	{
		printf("Error: First/second vertex was not found\n");
		return;
	}

	if (first_vertex_id == -2 || second_vertex_id == -2)
	{
		printf("Error: More than one vertex with the requested name exists, please add edge using vertex id\n");
		return;
	}

	add_edge_by_id(first_vertex_id, second_vertex_id, weight);
}

void add_edge_by_id (int head_vertex_id, int tail_vertex_id, double weight)
{
	int index_to_insert;

	if (head_vertex_id < 0 || tail_vertex_id < 0 || head_vertex_id >= allocated_vertexes || tail_vertex_id >= allocated_vertexes || arr_vertex[head_vertex_id]->deleted == 1 || arr_vertex[tail_vertex_id]->deleted == 1)
	{
		printf("Error: First/second vertex was not found\n");
		return;
	}

	
	if (head_vertex_id == tail_vertex_id)
	{
		printf("Error: No self loops are allowed in the network\n");
		return;
	}

	if (edge_already_exists(head_vertex_id,tail_vertex_id))
	{
		printf("Error: No duplicated edges are allowed in the network\n");
		return;
	}

	if (weight < 0)
	{
		printf("Error: When adding an edge weight must be positive\n");
		return;
	}


	allocate_edges_if_needed();
	index_to_insert = get_index_of_next_available_edge();

	arr_edges[index_to_insert]->deleted = 0;
	arr_edges[index_to_insert]->v1_id = head_vertex_id;
	arr_edges[index_to_insert]->v2_id = tail_vertex_id;
	arr_edges[index_to_insert]->weight = weight;

	number_of_available_edges--;

}

void remove_edge(int id)
{
	if (id < 0 || id >= allocated_edges || arr_edges[id]->deleted == 1)
	{
		printf("Error: Requested edge does not exist\n");
		return;
	}

	arr_edges[id]->deleted = 1;
	number_of_available_edges++;
}

void cluster(int num_of_clusters)
{
	int i;
	double cluster_score = 0;
	if(num_of_clusters < 1) {
		printf("Error: Number of clusters must be a number bigger or equal to 1\n");
		return; 	
	}
	srand ( time(NULL) );
	for (i = 0 ; i < allocated_vertexes; i++)
	{
		if (arr_vertex[i]->deleted == 0)
		{
			arr_vertex[i]->cluster = rand() % num_of_clusters;
		}
	}

	for (i = 0 ; i < allocated_edges ; i++)
	{
		if (arr_edges[i]->deleted == 0)
		{
			if (arr_vertex[arr_edges[i]->v1_id]->cluster == arr_vertex[arr_edges[i]->v2_id]->cluster)
			{
				cluster_score += arr_edges[i]->weight;
			}
			else
			{
				cluster_score -= arr_edges[i]->weight;
			}
		}
	}

	printf("%d vertices\n", allocated_vertexes - number_of_available_vertexes);
	for (i = 0 ; i < allocated_vertexes; i++)
	{
		if (arr_vertex[i]->deleted == 0)
		{
			printf("%d: %s %d\n", i, arr_vertex[i]->name, arr_vertex[i]->cluster);
		}
	}

	if (allocated_edges - number_of_available_edges > 0)
	{
		printf("%d edges\n", allocated_edges - number_of_available_edges);

		for (i=0; i < allocated_edges ;i++)
		{
			if (arr_edges[i]->deleted == 0)
			{
				printf("%d: %s-%s %.3f \n", i, arr_vertex[arr_edges[i]->v1_id]->name, arr_vertex[arr_edges[i]->v2_id]->name, arr_edges[i]->weight);
			}
		}
	}

	printf("The random clustering score for %d clusters is %.3f \n", num_of_clusters, cluster_score);
}

void quit()
{
	int i;
	for (i = 0 ; i < allocated_vertexes ; i++)
	{
		if (arr_vertex[i]->name != NULL)
		{
			free(arr_vertex[i]->name);
		}

		free(arr_vertex[i]);
	}

	for (i = 0 ; i < allocated_edges ; i++)
	{
		free(arr_edges[i]);
	}

	free(arr_edges);
	free(arr_vertex);
}

void print()
{
	int i;
	printf("%d vertices\n", allocated_vertexes - number_of_available_vertexes);
	for (i = 0 ; i < allocated_vertexes; i++)
	{
		if (arr_vertex[i]->deleted == 0)
		{
			printf("%d: %s\n", i, arr_vertex[i]->name);
		}
	}

	if (allocated_edges - number_of_available_edges > 0)
	{
		printf("%d edges\n", allocated_edges - number_of_available_edges);

		for (i=0; i < allocated_edges ;i++)
		{
			if (arr_edges[i]->deleted == 0)
			{
				printf("%d: %s-%s %.3f \n", i, arr_vertex[arr_edges[i]->v1_id]->name, arr_vertex[arr_edges[i]->v2_id]->name, arr_edges[i]->weight);
			}
		}
	}
}

void allocate_vertexes_if_needed()
{
	vertex **arr_vertex_temp;
	int i;
	if (number_of_available_vertexes == 0)
	{
		arr_vertex_temp = (vertex **)realloc(arr_vertex, (allocated_vertexes + MAX_ARRAY_SIZE) * sizeof(vertex*));
		if (arr_vertex_temp != NULL)
		{
			arr_vertex = arr_vertex_temp;
			for (i = allocated_vertexes ; i < allocated_vertexes + MAX_ARRAY_SIZE; i++)
			{
				arr_vertex[i] = (vertex*)malloc(sizeof(vertex));
				if (arr_vertex[i] == NULL)
				{
				 printf("Error: Memory allocation failed\n");
				}

				arr_vertex[i]->deleted = 1;
				arr_vertex[i]->cluster=-1;
				arr_vertex[i]->name = NULL;
			}

			allocated_vertexes += MAX_ARRAY_SIZE;
			number_of_available_vertexes+= MAX_ARRAY_SIZE;
		}
		else
		{
			printf("Error: Memory allocation failed\n");
		}
	}
}

void allocate_edges_if_needed()
{
	edge **arr_edge_temp;
	int i;
	if (number_of_available_edges == 0)
	{
		arr_edge_temp = (edge **)realloc(arr_edges, (allocated_edges + MAX_ARRAY_SIZE) * sizeof(edge*));
		if (arr_edge_temp != NULL)
		{
			arr_edges = arr_edge_temp;
			for (i = allocated_edges ; i < allocated_edges + MAX_ARRAY_SIZE; i++)
			{
				arr_edges[i] = (edge*)malloc(sizeof(edge));
				if (arr_edges[i] == NULL)
				{
				 printf("Error: Memory allocation failed\n");
				}

				arr_edges[i]->deleted = 1;
				arr_edges[i]->v1_id = -1;
				arr_edges[i]->v2_id = -1;
				arr_edges[i]->weight = -1;
			}

			allocated_edges += MAX_ARRAY_SIZE;
			number_of_available_edges+= MAX_ARRAY_SIZE;
		}
		else
		{
			printf("Error: Memory allocation failed\n");
		}
	}
}

int get_index_of_next_available_vertex()
{
	int i;
	for (i = 0 ; i < allocated_vertexes ; i++)
	{
		if (arr_vertex[i]->deleted == 1)
		{
			return i;
		}
	}
	return 0;
}

int get_index_of_next_available_edge()
{
	int i;
	for (i = 0 ; i < allocated_edges ; i++)
	{
		if (arr_edges[i]->deleted == 1)
		{
			return i;
		}
	}
	return 0;
}

int ToXGMMLFile(int k, char *  outputFolder, int isLowerBound, int * vertex_sol, int *cluster_sizes)
{
	xmlNodePtr root_node = NULL, node = NULL, edge = NULL, graphicsNode = NULL, nextSibling = NULL;/* node pointers */
	char buffer[512];
    int i, colorNumber, status=0, vertixes_cnt;
	vertixes_cnt = get_number_of_vertex();
	if (isLowerBound)
	{
		// doc = xmlNewDoc(BAD_CAST "1.0");
		 // root_node = xmlNewNode(NULL, BAD_CAST "graph");
       // xmlDocSetRootElement(doc, root_node);
        /*xmlNewProp(root_node, BAD_CAST "directed", BAD_CAST "0");
        xmlNewNs(root_node, BAD_CAST "http://www.cs.rpi.edu/XGMML", NULL);
        xmlNewNs(root_node, BAD_CAST "http://www.w3.org/1999/xlink", BAD_CAST "xlink");
        xmlNewNs(root_node, BAD_CAST "http://www.w3.org/1999/02/22-rdf-syntax-ns#", BAD_CAST "rdf");
        xmlNewNs(root_node, BAD_CAST "http://purl.org/dc/elements/1.1/", BAD_CAST "dc");
        xmlNewNs(root_node, BAD_CAST "http://www.cytoscape.org", BAD_CAST "cy");
        xmlNewProp(root_node, BAD_CAST "label", BAD_CAST buffer);*/
		
	}

	for (i = 0 ; i < vertixes_cnt; i++)
	{
		if (isLowerBound)
		{
			node = xmlNewChild(root_node, NULL, BAD_CAST "node", NULL);
			xmlNewProp(node, BAD_CAST "label", BAD_CAST arr_vertex[i]->name);
			xmlNewProp(node, BAD_CAST "id", BAD_CAST buffer);
			graphicsNode = xmlNewChild(node, NULL, BAD_CAST "graphics", NULL);
			xmlNewProp(graphicsNode, BAD_CAST "type", BAD_CAST "ELLIPSE");
            getColorHex(buffer, i);
            xmlNewProp(graphicsNode, BAD_CAST "fill", BAD_CAST buffer);
            xmlNewProp(graphicsNode, BAD_CAST "width", BAD_CAST "4");
            xmlNewProp(graphicsNode, BAD_CAST "cy:nodeLabel", BAD_CAST arr_vertex[i]->name);
            xmlNewProp(graphicsNode, BAD_CAST "cy:borderLineType", BAD_CAST "solid");
		}
		else
		{
			colorNumber = getColorHex(buffer, i);
            
            if (bound == 'U' && colorNumber > 5){
                
                nextSibling = xmlNextElementSibling(node);
                
                xmlUnlinkNode(node);
                xmlFreeNode(node);
                node = nextSibling;
                continue;
            }
            
            graphicsNode = xmlFirstElementChild(node);
            xmlSetProp(graphicsNode, BAD_CAST "fill", BAD_CAST buffer);
            node = xmlNextElementSibling(node);
		}
	}
}

int turn_solution_to_arrays(int number_of_clusters, double *x ,int **vertexes_sol_p, int **cluster_sizes_p )
{
	int edges_cnt, vertexes_cnt, i,j;
	int * vertexes_sol, *cluster_sizes;
	int id;
	edges_cnt = get_number_of_edges();
    vertexes_cnt = get_number_of_vertex();
	vertexes_sol = (int *)malloc(sizeof(int) * vertexes_cnt);
	cluster_sizes = (int *)malloc(sizeof(int) * number_of_clusters);
	memset(cluster_sizes, 0,  sizeof(int) * number_of_clusters);
	memset(vertexes_sol, 0,  sizeof(int) * vertexes_cnt);

	for (i = 0;i<vertexes_cnt;++i) {
		for (j=0;j<number_of_clusters;++j) {
			id = number_of_clusters*edges_cnt + (i*number_of_clusters) + j;						
			if (IS_VALUE_1(x[id]) ) {
				vertexes_sol[i]=j;
				cluster_sizes[j]++;
			} 
		}
	}

	*vertexes_sol_p = vertexes_sol;
	*cluster_sizes_p = cluster_sizes;
	return 1;
}


int buildClustersColorsArray(int nClusters)
{

}

/*returns the index of a vertex with the given name. if no vertex exists, returns -1. if more then one match, returns -2 */
int get_vertex_id(char* name)
{
	int i;
	int index = -1;

	for (i = 0; i < allocated_vertexes ; i++)
	{
		if (arr_vertex[i]->deleted == 0 && strcmp(arr_vertex[i]->name, name) == 0)
		{
			if (index != -1)
			{
				return -2;
			}
			else
			{
				index = i;
			}
		}
	}
	
	return index;
}

bool edge_already_exists(int first_vertex_id, int second_vertex_id)
{
	int i;
	for (i =0 ;i < allocated_edges; i++)
	{
		if (arr_edges[i]->deleted == 0)
		{
			if ((arr_edges[i]->v1_id == first_vertex_id && arr_edges[i]->v2_id == second_vertex_id) ||
				(arr_edges[i]->v2_id == first_vertex_id && arr_edges[i]->v1_id == second_vertex_id))
			{
				return true;
			}
		}
	}

	return false;
}

int get_number_of_vertex()
{
	return allocated_vertexes - number_of_available_vertexes;
}

int get_number_of_edges()
{
	return allocated_edges - number_of_available_edges;
}

vertex** get_vertexes()
{
	return arr_vertex;
}

edge ** get_edges()
{
	return arr_edges;
}

int getVertexID(int e, int v)
{
    if (v > 1)
    {
        return v;
    }
    return (v==0) ? arr_edges[e]->v1_id : arr_edges[e]->v2_id;
}